package dp;

/**
 * LCP 07. 传递信息
 */
public class PLC07 {
    public int numWays(int n, int[][] relation, int k) {
        if (k == 0) {
            return 1;
        }
        int[][] dp = new int[k][n];
        for (int[] rel : relation) {
            if (rel[0] == 0) {
                dp[0][rel[1]] = 1;
            }
        }
        for (int i = 0; i < k-1; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] != 0) {
                    for (int[] rel : relation) {
                        if (rel[0] == j) {
                            dp[i + 1][rel[1]] += dp[i][j];
                        }
                    }
                }
            }
        }
        return dp[k-1][n - 1];
    }

    public static void main(String[] args) {
        int n = 5;
        int k = 3;
        int[][] relation = new int[][]{
                {0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}
        };

        int count = new PLC07().numWays(n, relation, 3);
        System.out.println(count);
    }
}
